/// @tags: MatrixAcceleration
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define rint register int

using std::cin;
using std::cout;

namespace BlueQuantum {

constexpr int MAXN = 53, MAXM = 63, P = 45989;

inline int inc(int a, int b) {
  a += b;
  return a >= P ? a - P : a;
}

int n, m, S, T, t, ecnt = -1;
int heads[MAXN];

struct Matrix {
  int a[MAXM * 2][MAXM * 2];

  inline Matrix(int x = 0) {
    for (rint i = 0; i <= ecnt; ++i)
      for (rint j = 0; j <= ecnt; ++j) a[i][j] = i == j ? x : 0;
  }

  inline int *operator[](int index) { return a[index]; }
  inline const int *operator[](int index) const { return a[index]; }

  inline Matrix operator*(const Matrix &rhs) const {
    Matrix res;
    for (rint i = 0; i <= ecnt; ++i)
      for (rint j = 0; j <= ecnt; ++j)
        for (rint k = 0; k <= ecnt; ++k) res[i][j] = inc(res[i][j], a[i][k] * rhs[k][j] % P);
    return res;
  }

  inline Matrix operator^(int exp) const {
    Matrix res(1), base(*this);
    for (; exp; exp >>= 1, base = base * base)
      if (exp & 1) res = res * base;
    return res;
  }
};

struct Edge {
  int v, nxt;
} e[MAXM * 2];

inline void add(int u, int v) { e[++ecnt].v = v, e[ecnt].nxt = heads[u], heads[u] = ecnt; }

inline int main() {
  memset(heads, -1, sizeof(heads));
  cin >> n >> m >> t >> S >> T;
  for (rint i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    add(u, v), add(v, u);
  }
  Matrix trans, ini;
  for (rint i = 0; i <= ecnt; ++i) {
    for (rint j = heads[e[i].v]; j >= 0; j = e[j].nxt) {
      if (j != (i ^ 1)) trans[i][j]++;
    }
  }
  for (rint i = heads[S]; i >= 0; i = e[i].nxt) ini[0][i]++;
  trans = ini * (trans ^ (t - 1));
  int ans = 0;
  for (rint i = heads[T]; i >= 0; i = e[i].nxt) ans = inc(ans, trans[0][i ^ 1]);
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P2151 [SDOI2009] HH去散步.in", "r", stdin);
  freopen("P2151 [SDOI2009] HH去散步.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
